#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


void getString(int left, int right, const string &rtn, vector<string> &ans, int target)
{
    if (left == target && right == target) {
        ans.push_back(rtn);
        return;
    } else if (right > target || left > target || left < right) {
		return;
	}

    if (left == right) {
        getString(left + 1, right , rtn + '(',  ans, target);
    } else {
        getString(left + 1, right , rtn + '(',  ans, target);
        getString(left, right+1 , rtn + ')',  ans, target);
	}
}

class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> ans;
            int left = 0, right = 0;
            string rtn;
            getString(left, right, rtn, ans, n);
            return ans;
        }
};

void getString2(int l, int r, string s, vector<string> &result)
{
    if (l ==0 && r == 0) result.push_back(s);
    if (l > 0) getString2(l-1, r, s + '(', result);
    if (r > l) getString2(l, r-1, s+')', result);
}

class Solution1 {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> ans;
            getString2(n, n, "", ans);
            return ans;
        }
};

int main(int argc, char **argv)
{
    Solution mySolution;
    vector<string> result;
    result = mySolution.generateParenthesis(3);
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << endl;
	return 0;
}
